package cn.fansunion.leecode.recursion;

/**
 * 1137. 第 N 个泰波那契数 <br/>
 * 泰波那契序列 Tn 定义如下： <br/>
 * T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2<br/>
 * 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。<br/>
 * 
 * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/n-th-tribonacci-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 * @author wen.lei@brgroup.com
 *
 *         2022-3-9
 */
public class NthTribonacciNumber {
    /* 示例 1：
    
    输入：n = 4
    输出：4
    解释：
    T_3 = 0 + 1 + 1 = 2
    T_4 = 1 + 1 + 2 = 4
    示例 2：
    
    输入：n = 25
    输出：1389537
     
    
    提示：
    
    0 <= n <= 37
    答案保证是一个 32 位整数，即 answer <= 2^31 - 1。*/
    public int tribonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else {
            // t(n)=t(n-3)+t(n-2)+t(n-1)
            return tribonacci(n - 3) + tribonacci(n - 2) + tribonacci(n - 1);
        }
    }

    public int tribonacciDp(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        }
        // 额外维护1个数组，看起来更清晰
        int[] array = new int[n + 1];
        array[0] = 0;
        array[1] = 1;
        array[2] = 1;
        for (int index = 3; index <= n; index++) {
            // t(n)=t(n-3)+t(n-2)+t(n-1)
            array[index] = array[index - 3] + array[index - 2] + array[index - 1];
        }
        return array[n];
    }
}
